package com.gorkr.offer.dp;

import org.junit.jupiter.api.Test;

/**
 *
 * 剪绳子
 * 动归好理解 贪心做法 见leetcode343整数拆分
 * @author gorkr
 * @date 2022/07/24 10:54
 **/
public class M14JianShengZiI {

    public int cuttingRope(int n) {

        // dp 数组定义 dp[i] 是把长度为i的绳子 剪成m段的 最大乘积
        int[] dp = new int[n + 1];
        // basecase todo 越界的问题
        dp[0] = 0; dp[1] = 1; dp[2]=1;

        for (int i = 3; i <= n ; i++) {
            // 第一刀割哪儿
            for (int j = 2; j <i; j++) {
                dp[i] = Math.max(dp[i],Math.max(j*dp[i-j],j*(i-j)));
            }

        }
        return dp[n];
    }
    @Test
    public void test(){
        System.out.println(cuttingRope(10));
    }

}
    